Get started, Permutations and Combinations
In elementary probability, one of the most important things is to count the number of possible outcomes of a certain event or experiment. To achieve that, we need to understand permutations and combinations.
We start with a simple problem:
Problem: A tire manufacturer wants to test four different types of tires on three different types of roads at five different speeds. How many tests are required?
We begin by noting that there are 4*3=12 possible combinations of tires and roads. Each of these can be paired with one of the five different speeds. So the answer is there are 4*3*5=60 different ways to match types of tire, road and speed.
The reasoning above can be easily extended to experiments beyond three stages to choose and does not depend on the number of choices at each stage. So we generalize the observation to a useful principle :
The multiplication rule: Suppose that m experiments are carried out in order and no matter what the outcomes of the first 1,2,..., k-1 experiments are, experiment k has n-k possible outcomes. Then the total number of outcomes is the product of the number of outcomes at each stage.
Let’s consider another problem,
Problem: how many possible batting orders are there for 9 baseball players?
To consider this problem, we imagine that first we put the 9 players in a line and they go in order. To build the line, there are 9 people we can choose from to put at the front. Having made the first decision, we have 8 choices for the second position. Continuing, there are 7 choices for the third position and finally 1 choice for the last position. Using the multiplication rule, we see that the answer is 9*8*...*1=9!
Here we define n!:=n*(n-1)*...*1, called n factorial. The above argument can be easily generated and we see that the number of ways of putting n people in a line is n!. Notice that n factorial grows very fast as n grows bigger.
Sometimes we need to pick k individuals from a group of size n, and the order of picking up is not important. As in the next problem:
Problem: In a class of 19 students, 7 of them will get 'A'. In how many ways can this set of students be chosen?
To reduce this problem to the case we considered, we still imagine making the 'A' students stand in a line. There are 19*18*...*13 ways of lines. And each set selected can stand in 7!=7*6*...*1 different orders. So the number of different sets is the number of lineups divided by 7!, that is 19*18*...*13/(7*6*...*1).
More generally, we denote by C_n,k the number of combinations of k things taken from a set of size n. And generalize the above reasoning, we have a useful formula:
C_n,k = n*(n-1)*...*(n-k+1)/k*(k-1)*...*1
Counting possible outcomes is the basic way to compute probability.Let's look at the following problem.
Problem: Suppose we flip 5 coins. Compute the probability of getting 0,1 or 2 heads.
First notice that by the multiplication rule, the total number of outcomes is 2^5=32. Obviously there is only one way to get 0 heads (all the outcomes are tails), so the probability of getting 0 heads is 1/32. Note that C_5,0=1. There are 5 outcomes with 1 head, we can write them out explicitly: HTTTT, THTTT,TTHTT,TTTHT,TTTTH. Or note that the number of picking up 1 head out of 5 tosses is C_5,1=5/1=5. So the probability of getting 1 head is 5/32. For the case of 2 heads, we have that pick up 2 heads out of 5 tosses is C_5,2=5*4/2*1=10. Then the probability of getting 2 heads is 10/32.
Remark: Combination numbers have the following symmetry property: C_n,m=C_n,n-m. You can prove this by either looking at the formula or arguing that pick up m things from a set of size n is the same as decide the n-m things to be left behind.